package com.xypower.sort;

import java.util.concurrent.CountDownLatch;
//桶排序
public class radixSortTest {
    public static void radixSort(int[] arr){
        if (arr==null||arr.length<2){
            return;
        }
        radixSort(arr,0,arr.length-1,maxbits(arr));
    }
    //返回最大值的10进制
    public static int maxbits(int[] arr){
        int max = Integer.MIN_VALUE;
        for (int i =0; i<arr.length;i++){
            max = Math.max(max,arr[i]);
        }
        int res = 0;
        while (max != 0){
            res++;
            max /= 10;
        }
        return res;
    }
    //digit 最大值有几个十进制位
    public static void radixSort(int[] arr,int L,int R,int digit){
        final int radix = 10;
        int i=0,j=0;
        //有多少个数准备多少个辅助空间
        int[] bucket = new int[R - L + 1];
        for (int d=1;d<=digit;d++){
            //10个空间
            //count[0] 当前位(d位)是0的数字有多少个
            //count[1] 当前位(d位)是(0和1)的数字有多少个
            //count[2] 当前位(d位)是(0、1和2)的数字有多少个
            //count[i] 当前位(d位)是(0-i)的数字有多少个
            int[] count = new int[radix];   //count[0...9]
            //得到哪一位则以那一位为下标计数+1   =i   词频数组
            for (i=L;i<=R;i++){
                j=getDigit(arr[i],d);
                count[j]++;
            }
//            后一位等于前面数累加和     <=i    前缀和数组
            for (i=1;i<radix;i++){
                count[i] = count[i]+count[i-1];
            }
            //从右边开始遍历，排序到桶中
            for (i=R;i>=L;i--){
                j = getDigit(arr[i],d);
                bucket[count[j]-1]=arr[i];
                count[j]--;
            }
            //覆盖原数组
            for (i=L,j=0;i<=R;i++,j++){
                arr[i]  =bucket[j];
            }
        }

    }
    //获取某一位
    public static int getDigit(int x,int d){
        return ((x/((int) Math.pow( 10 , d - 1 ))) % 10);
    }
}
